package com.cskaoyan.javase.hanoi;

/**
 * @description: 汉诺塔问题递归求解
 * @author: wuguidong@cskaoyan.onaliyun.com
 **/

/**
 * 简单来说：有三个塔1，2，3，塔1上有 N 个（N>1）穿孔圆盘，大盘在下，小盘在上
 * 要求按下列规则将所有圆盘移至塔3：
 * ​	1，每次只能移动一个圆盘
 * ​	2，大盘一定在小盘之下
 * 将塔1的所有盘子 放到 塔3
 * 玩两把，总结规律：
 * 当n=1，这时候直接从塔1拿到塔3，需要1步
 * 当n=2，我把小盘从塔1拿到塔2，把大盘从塔1拿到塔3，然后再把小盘从塔2拿到塔3
 * 当n=3，先把最小的盘子从塔1移到塔3，再把中间的盘子移到塔2，然后把最小的盘子移到塔2，
 * 把大盘移到塔3
 * 把小盘子从塔2移到塔1，再把塔2上的中间的盘子放到塔3，把塔1上的小盘子放到塔3
 * ....
 *
 * 实际上无论n等于几，都可以总结出一个规律
 * 第一部分：把除了最大的盘子之外的所有盘子，都移到辅助的塔2中
 * 第二部分：把大盘从塔1移到塔3
 * 第三部分：再通过塔1去辅助，把塔2中除了最大盘子之外的所有盘子，移到塔3
 *
 * 假设用一个函数来表示
 * 需要f(N)步来完成我的汉诺塔问题
 * F(N) = F(N-1) + 1 + F(N-1)
 * ....
 * F（1） = 1
 *
 * 通过数学的方法求解出这个F(N) = F(N-1) + 1 + F(N-1)的通项公式
 * 高考
 * 等比数列：
 * f(n) + 1 = f(n-1) + 2 + f(n-1)
 * f(n) + 1 = 2(f(n-1)+1)
 * f(n)+1/f(n-1)+1 = 2
 * f(n)+1 = 2的n次方
 * f(n) = 2^n -1
 *
 *
 *
 *
 *
 */
public class Demo {
    public static void main(String[] args) {
        System.out.println(hanoi(4));
    }

    //通过公式来写我们的递归算法
    public static long hanoi(int n) {
        //递归出口
        if (n == 1) {
            return 1;
        } else {
            long count1 = hanoi(n - 1);
            long count2 = 1;
            long count3 = hanoi(n - 1);
            return count1 + count2 + count3;
        }
    }
}
